package com.zq.solution.algorithm.dynamicProgramming;

import java.util.Arrays;
import java.util.List;

/**
 * @ClassName MinimumTotal
 * @Description 动态规划解三角形最小路径和问题
 * 120. 三角形最小路径和
 *   给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
 *   相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
 * 例如，给定三角形：
 * [
 *      [2],
 *     [3,4],
 *    [6,5,7],
 *   [4,1,8,3]
 * ]
 * 自顶向下的最小路径和为11（即，2 + 3 + 5 + 1 = 11）。
 * @Author ZQ
 * @Date 2020/12/10 16:19
 * @Version 1.0
 */
public class MinimumTotal {
    public int minimumTotal(List<List<Integer>> triangle) {//动态规划 + 递归（运行时间太长没过）

        return minimumTotal(triangle,0,0,triangle.size());
    }
    public int minimumTotal(List<List<Integer>> triangle,int row,int col,int length) {
        if (row >= length || col >= length) return 0;
        int left = minimumTotal(triangle,row + 1, col,length);
        int right = minimumTotal(triangle,row + 1, col + 1,length);

        return triangle.get(row).get(col) + Math.min(left,right);
    }

    public static int minimumTotal1(List<List<Integer>> triangle) {//动态规划 + 非递归
        int n = triangle.size();
        int[][] f = new int[n][n];
        f[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; ++i) {
            f[i][0] = f[i - 1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; ++j) {
                f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j);
            }
            f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);
        }
        int minTotal = f[n - 1][0];
        for (int i = 1; i < n; ++i) {
            minTotal = Math.min(minTotal, f[n - 1][i]);
        }
        return minTotal;
    }


    public static void main(String[] args) {
        List<Integer> l1 = Arrays.asList(-1);
        List<Integer> l2 = Arrays.asList(2,3);
        List<Integer> l3 = Arrays.asList(1,-1,-3);
//        List<Integer> l4 = Arrays.asList(4,1,8,3);
        List<List<Integer>> triangle = Arrays.asList(l1,l2,l3);

//        System.out.println(new MinimumTotal().minimumTotal(triangle));
        System.out.println(minimumTotal1(triangle));
    }
}
